#include <iostream>

template <typename T>
struct LinkNode {
    T val;
    LinkNode* next = NULL;
    LinkNode* pre = NULL;
};

// 头插法
template <typename T>
void insert_head(LinkNode<T>* src, T val)
{
    LinkNode<T>* node = new LinkNode<T>;
    node->val = val;
    if(src->next)
    {
        node->next = src->next;
        src->next->pre = node;
        src->next = node;
        node->pre = src;
    }
    else
    {
        node->next = src->next;
        src->next = node;
        node->pre = src;
    }
}

// 尾插法
template <typename T>
void insert_end(LinkNode<T>* src, T val)
{
    LinkNode<T>* node = new LinkNode<T>;
    node->val = val;

    while(src->next)
    {
        src = src->next;
    }

    node->next = src->next;
    src->next = node;
    node->pre = src;
}

// 第idx个位置前插入结点，有头结点，idx>0
template <typename T>
void insert_val_by_idx(LinkNode<T>* src, unsigned int idx, T val)
{
    LinkNode<T>* node = new LinkNode<T>;
    node->val = val;

    unsigned int count = 0;
    while(src && src->next)
    {
        if(idx-1 == count)
        {
            node->next = src->next;
            src->next->pre = node;
            src->next = node;
            node->pre = src;
            break;
        }
        count += 1;
        src = src->next;
    }
}

// 删除第idx个位置的结点,idx>0
template <typename T>
void del_val_by_node(LinkNode<T>* src, unsigned int idx)
{
    unsigned int count = 0;
    while(src && src->next)
    {
        if(idx-1 == count)
        {
            LinkNode<T>* node = src->next;
            if(!src->next->next)
                src->next = NULL;
            else
            {
                src->next->next->pre = src;
                src->next = src->next->next;
            }
            node->pre = NULL;
            node->next = NULL;
            delete node;
            break;
        }
        count += 1;
        src = src->next;
    }
}

// 注销
template <typename T>
void release(LinkNode<T>* src)
{
    while(src)
    {
        LinkNode<T>* node = src;
        src = src->next;
        node->next = NULL;
        node->pre = NULL;
        delete node;
    }
}

int main()
{
    LinkNode<int>* head = new LinkNode<int>;
    head->val = -1;

    for(int i = 0; i < 5; i++)
    {
        // insert_head(head, i);
        insert_end(head, i);
    }
    insert_val_by_idx(head, 2, 100);
    del_val_by_node(head, 6);

    // while(head)
    // {
    //     std::cout << head->val << " ";
    //     if(head->pre)
    //         std::cout << head->val << " pre is " << head->pre->val << std::endl;
    //     head = head->next;
    // }
    release(head);
    return 0;
}